package com.lw.leetcode.add.e;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 837. 新 21 点
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/22 11:30
 */
public class New21Game {

    public static void main(String[] args) {
        New21Game test = new New21Game();

        // 1.00000
//        int n = 10;
//        int k = 1;
//        int maxPts = 10;

        // 0.60000
//        int n = 6;
//        int k = 1;
//        int maxPts = 10;

        // 0.73278
//        int n = 21;
//        int k = 17;
//        int maxPts = 10;

        // 0.65820
        int n = 6;
        int k = 5;
        int maxPts = 4;

        double v = test.new21Game(n, k, maxPts);
        System.out.println(v);
    }

    public double new21Game(int n, int k, int maxPts) {
        int length = k + maxPts;
        int[] arr = new int[length + 1];
        arr[0] = 1;
        arr[maxPts + 1] = -1;
        for (int i = 1; i < k; i++) {
            arr[i] += arr[i - 1];
            int t = arr[i];
            arr[i + 1 ] += t;
            arr[i + maxPts + 1] -= t;
        }
        double b = 0;
        for (int i = k; i < length; i++) {
            arr[i] += arr[i - 1];
        }
        System.out.println(Arrays.toString(arr));
        for (int i = k; i <= n; i++) {
            b += arr[i];
        }
        double a = b;
        for (int i = n + 1; i < length; i++) {
            b += arr[i];
        }
        return a / b;
    }
}



